package william.array;

/**
 * @author ZhangShenao
 * @date 2024/4/9
 * @description <a href="https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode53_最大子数组和 {
    /**
     * 采用动态规划算法
     * 遍历数组,记录前序和preSum。
     * 针对当前元素nums[i],根据preSum的大小,决定是将当前元素追加到preSum中,还是抛弃preSum,从当前元素开始重新记录preSum。
     * 状态转移公式: dp[i] = Max{ (dp[i-1]+nums[i]) , nums[i] }
     * 初始解空间: dp[0]=nums[0]
     * <p>
     * 时间复杂度O(N) 只遍历一次数组
     * 空间复杂度O(1)
     */
    public int maxSubArray(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //记录前序和preSum和最大和maxSum
        int preSum = nums[0];
        int maxSum = nums[0];

        //遍历数组
        for (int i = 1; i < nums.length; i++) {
            //根据preSum的大小,判断是将当前元素追加到preSum中,还是抛弃preSum,以当前元素为起点开始新的preSum
            preSum = Math.max(preSum + nums[i], nums[i]);

            //更新最大和
            maxSum = Math.max(maxSum, preSum);
        }


        //返回最大和
        return maxSum;
    }
}
